import java.util.Map;
import java.util.LinkedHashMap;
import java.util.Iterator;
import java.lang.NullPointerException;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

public class QueueUtil {

    static public class KeyedValue<K, V> {
        private K m_key;
        private V m_val;

        public KeyedValue(K k1, V v1) {
            m_key = k1;
            m_val = v1;
        }
        public K getKey() {
            return m_key;
        }

        public V getValue() {
            return m_val;
        }
    }


    public interface ConflatingQueue<K, V> {
        /**
         * Adds a keyed value to the queue.
         *
         * If a keyed value already exists in the queue with the same key, then the old value in the queue is updated
         * in place with the new value. The order of the new value within the queue should be the same as the old value.
         *
         * If no keyed value exists in the queue with the same key, the value is added to the end of the queue.
         *
         * @param value the keyed value to add to the queue
         * @return true if the keyed value could be added to the queue, false otherwise
         * @throws NullPointerException if value is null
         */
        boolean offer(KeyedValue<K, V> value);
    
        /**
         * Removes the first keyed value in the queue, blocking if the queue is empty.
         *
         * @return the first keyed value in the queue
         * @throws InterruptedException if the thread was interrupted while waiting for a keyed value to be added to the queue
         */
        KeyedValue<K, V> take() throws InterruptedException;
    
        /**
         * Checks whether the queue is currently empty
         *
         * @return true if the queue is currently empty, false otherwise
         */
        boolean isEmpty();
    }

    static public class KeyQueue<K, V> implements ConflatingQueue<K, V> {
        private LinkedHashMap<K, KeyedValue<K, V>> mapQueue = new LinkedHashMap<K, KeyedValue<K, V>>();
        private ReentrantLock queueLock = new ReentrantLock();
        private Condition waitCond = queueLock.newCondition();
    
        @Override
        public boolean offer(KeyedValue<K, V> value) {
            if (value == null){
                throw new NullPointerException();
            }
            queueLock.lock();
            try {
                mapQueue.put(value.getKey(), value);
                waitCond.signal();
            }
            catch(IllegalMonitorStateException e) {
                System.out.println(e.getMessage());
                return false;
            }
            finally {
                queueLock.unlock();
            }
            return true;
        }
    
        @Override
        public KeyedValue<K, V> take() throws InterruptedException {
            queueLock.lock();
            try {
                while (mapQueue.isEmpty()) {
                    waitCond.await();
                }
                Iterator<Map.Entry<K, KeyedValue<K, V>>> iterator= mapQueue.entrySet().iterator();
                if (iterator.hasNext()) {
                    Map.Entry entry = iterator.next();
                    iterator.remove();
                    return (KeyedValue<K, V>)entry.getValue();
                }
            }
            catch(InterruptedException e) {
                throw e;
            }
            finally {
                queueLock.unlock();
            }
            return null;
        }
    
        @Override
        public boolean isEmpty() {
            queueLock.lock();
            try {
                return mapQueue.isEmpty();
            }
            finally {
                queueLock.unlock();
            }
        }
    }
}